# -*-coding = utf-8 -*-

# @Time: 2021/4/5 15:06
# @Author: bistro
# @File: p88.py
# @Software: PyCharm
# 88.合并两个有序数组
from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        1. 40ms 14.8MB
        if m < len(nums1):
            for e in range(len(nums1) - m):
                nums1.pop()
        right = -1
        new_nums = nums1[::]
        for i in range(m):
            temp = new_nums[i]
            # print(temp, end="")
            for j in range(right + 1, n):
                # 左边比右边大
                if temp >= nums2[j]:
                    right = j
                    nums1.insert(nums1.index(temp), nums2[j])
                else:
                    break
        if right != n - 1:
            for k in range(right + 1, n):
                nums1.append(nums2[k])
        # print(nums1)

        2. 40ms 14.9MB
         # 末尾元素下标
        last = m + n - 1
        # 主要是需要遍历nums2数组,n=0代表遍历结束
        # 注意m=0,而n!=0的情况,也就是m中的普遍比n大的情况
        while n:

            if nums1[m - 1] <= nums2[n - 1] or m == 0:
                nums1[last] = nums2[n - 1]
                n -= 1
                last -= 1
            else:
                nums1[last] = nums1[m - 1]
                m -= 1
                last -= 1
        print(nums1)
        """
        if m < len(nums1):
            for e in range(len(nums1) - m):
                nums1.pop()
        right = -1
        new_nums = nums1[::]
        for i in range(m):
            temp = new_nums[i]
            # print(temp, end="")
            for j in range(right + 1, n):
                # 左边比右边大
                if temp >= nums2[j]:
                    right = j
                    nums1.insert(nums1.index(temp), nums2[j])
                else:
                    break
            if right == n - 1:
                break
        if right != n - 1:
            for k in range(right + 1, n):
                nums1.append(nums2[k])
        # print(nums1)

# 时间复杂度:O(n)
# 空间复杂度O(1)


s = Solution()
s.merge([0, 0, 3, 0, 0, 0, 0, 0, 0], 3, [-1, 1, 1, 1, 2, 3], 6)


